package lz;

import java.util.ArrayDeque;
import java.util.Objects;
import java.util.Queue;
import java.util.Stack;
import java.util.function.Supplier;

public class LZTree<T> {
    /**
     * 遍历链接的树
     */
    public void traversalLinkTree(Node<T> node) {
        if(null == node) {
            return;
        }

        Node<T> tmp = node;
//        preRootTraversal(node);
        layerTraversalTree(node);
        System.out.println("------------------------------------------");
        node = node.parent;
        while (node != tmp) {
//            preRootTraversal(node);
            layerTraversalTree(node);
            System.out.println("------------------------------------------");
            node = node.parent;
        }
    }

    /**
     * 构建N层满二叉树
     * 一边构建一边填充值
     * @param levels
     * @return
     */
    public Node<T> buildFullBinaryTreeWithValue(int levels, Supplier<T> supplier) {
        if (levels <= 0) {
            return null;
        }

        Node<T> root = new Node(supplier.get());

        if(levels == 1) {
            return root;
        }

        //层数量
        int level = 1;
        //当前层的节点数
        int curLayerNodeNum = 1;
        //下一层的节点数
        int nextLayerNodeNum = 0;

        Queue<Node<T>> queue = new ArrayDeque<>();
        queue.add(root);

        while (level < levels && !queue.isEmpty()) {
            Node<T> node = queue.poll();
            curLayerNodeNum --;

            //添加左子节点
            Node<T> left = new Node<>(supplier.get());
            node.setLeft(left);
            queue.add(left);
            nextLayerNodeNum++;

            //添加右子节点
            Node<T> right = new Node<>(supplier.get());
            node.setRight(right);
            queue.add(right);
            nextLayerNodeNum++;

            if(curLayerNodeNum == 0) {
                level ++;
                curLayerNodeNum = nextLayerNodeNum;
                nextLayerNodeNum = 0;
            }
        }
        return root;
    }


    /**
     * 构建N层满二叉树
     * @param levels
     * @return
     */
    public Node<T> buildFullBinaryTree(int levels) {
        if (levels <= 0) {
            return null;
        }

        if(levels == 1) {
            return new Node<T>(null);
        }

        Node<T> root = new Node<>(null);
        //层数量
        int level = 1;
        //当前层的节点数
        int curLayerNodeNum = 1;
        //下一层的节点数
        int nextLayerNodeNum = 0;

        Queue<Node<T>> queue = new ArrayDeque<>();
        queue.add(root);

        while (level < levels && !queue.isEmpty()) {
            Node<T> node = queue.poll();
            curLayerNodeNum --;

            //添加左子节点
            Node<T> left = new Node<>(null);
            node.setLeft(left);
            queue.add(left);
            nextLayerNodeNum++;

            //添加右子节点
            Node<T> right = new Node<>(null);
            node.setRight(right);
            queue.add(right);
            nextLayerNodeNum++;

            if(curLayerNodeNum == 0) {
                level ++;
                curLayerNodeNum = nextLayerNodeNum;
                nextLayerNodeNum = 0;
            }
        }
        return root;
    }

    /**
     * 先根遍历
     */
    public void preRootTraversal(Node<T> root) {
        if(null == root) {
            return;
        }
        System.out.print(root.getData() + " ");
        if(null != root.left) {
            preRootTraversal(root.left);
        }

        if(null != root.right) {
            preRootTraversal(root.right);
        }
    }


    /**
     * 按层遍历树
     * 从上到下，从左到右
     * @param root
     */
    public void layerTraversalTree(Node<T> root) {
        Objects.requireNonNull(root, "root must be not null");

        Queue<Node<T>> queue = new ArrayDeque<>();
        queue.add(root);
        layerTraversal(queue);
    }

    /**
     * 递归每一层
     * @param queue
     */
    private void layerTraversal(Queue<Node<T>> queue) {
        if(null == queue || queue.isEmpty()) {
            return;
        }
        StringBuilder builder = new StringBuilder();
        Queue<Node<T>> nextLevelQueue = new ArrayDeque<>();
        while (!queue.isEmpty()) {
            Node<T> node = queue.poll();
            builder.append(node.getData() + " ");

            if(null != node.left) {
                nextLevelQueue.add(node.left);
            }

            if(null != node.right) {
                nextLevelQueue.add(node.right);
            }
        }
        //每层输出一次
        System.out.println(builder);
        layerTraversal(nextLevelQueue);
    }



    /**
     * 树节点内部类
     * @param <E>
     */
    public static class Node<E>{
        private E data;
        private Node<E> left;
        private Node<E> right;
        private Node<E> parent;

        public Node(E data) {
            this.data = data;
            this.left = null;
            this.right = null;
            this.parent = null;
        }

        public E getData() {
            return data;
        }

        public void setParent(Node<E> parent) {
            this.parent = parent;
        }

        /**
         * 需要维护父子关系
         * @param left
         */
        public void setLeft(Node<E> left) {
            if(this.left != null) {
                this.left.parent = null;
            }
            this.left = left;
            if(left != null) {
                left.setParent(this);
            }
        }

        /**
         * 需要维护父子关系
         * @param right
         */
        public void setRight(Node<E> right) {
            //当前节点的右孩子节点父指针设置为null
            if(null != this.right) {
                this.right.parent = null;
            }
            //右孩子
            this.right = right;
            //右孩子parent
            if(null != right) {
                right.setParent(this);
            }
        }
    }

    /**
     * 用队列的广度遍历
     */
    public void queueTraversal(Node<T> root) {
        if(null == root) {
            return;
        }
        Queue<Node<T>> queue = new ArrayDeque<>();
        queue.add(root);

        while (!queue.isEmpty()) {
            Node<T> node = queue.poll();
            if(null == node) {
                continue;
            }
            System.out.println(node.getData());

            if(null != node.left) {
                queue.add(node.left);
            }

            if(null != node.right) {
                queue.add(node.right);
            }
        }
    }

    /**
     * 非递归先根遍历
     */
    public void preDepthTraversal(Node<T> root) {
        if(null == root) {
            return;
        }
        Stack<Node<T>> stack = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            Node<T> node = stack.pop();
            System.out.print(node.getData() + " ");

            if(null != node.right) {
                stack.push(node.right);
            }

            if(null != node.left) {
                stack.push(node.left);
            }
        }
    }

    public void middleDepthTraversal(Node<T> root) {
        if(null == root) {
            return;
        }
        Stack<Node<T>> stack = new Stack<>();
        while (null != root || !stack.isEmpty()) {
            while (null != root) {
                stack.push(root);
                root = root.left;
            }

            if(!stack.isEmpty()) {
                Node<T> node = stack.pop();
                System.out.print(node.getData() + " ");
                root = node.right;
            }
        }
    }
}
